import org.junit.jupiter.api.Test;
import sun.awt.image.ImageWatched;

import java.util.*;

/**
 * @author ZhengDp
 * @Date 2023/4/3 17:36
 */
public class 栈_队列 {

    /*
    * #problem 20 有效的括号
    * */
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        for(int i = 0 ; i < s.length();i++) {
            Character c = s.charAt(i);
            if(c.equals('(') || c.equals('[') || c.equals('{')) {
                stack.addLast(c);
            } else {
                if(stack.isEmpty()) {
                    return false;
                }
                Character temp = stack.removeLast();
                if(c.equals(')') && temp.equals('(')) {
                    continue;
                } else if(c.equals(']') && temp.equals('[')) {
                    continue;
                } else if(c.equals('}') && temp.equals('{')) {
                    continue;
                } else {
                    return false;
                }
            }

        }
        return stack.isEmpty();
    }

    private Map<Character,Character> hash = new HashMap();
    {
        hash.put(')','(');
        hash.put(']','[');
        hash.put('}','{');
    }

    public boolean isValid1(String s) {
        Deque<Character> stack = new LinkedList();
        for(int i = 0 ; i < s.length();++i) {
            Character temp = s.charAt(i);
            if(hash.containsKey(temp)) {
                if(stack.isEmpty() || stack.pop() != hash.get(temp)) {
                    return false;
                }
            } else {
                stack.push(temp);
            }
        }

        return stack.isEmpty();
    }


    /*
    * #problem 84. 柱状图中最大的矩形
    * */
    // 1. 暴力解法，确定高，找两侧最长延申距离 (会超时）
    public int largestRectangleArea1(int[] heights) {
        int res = 0 ;
        for(int i = 0 ; i < heights.length;++i) {
            int h = heights[i];
            // 找左右边界
            int left = i-1,right = i+1;
            while(left > 0) {
                if(heights[left] >= h) {
                    left --;
                }
            }
            while(right < heights.length) {
                if(heights[right] >= h) {
                    right ++;
                }
            }
            res = Math.max(res,h*(right - left -1));
        }
        return res;
    }
    // 2. 暴力解法，遍历所有的边界 ==> 超时
    public int largestRectangleArea2(int[] heights) {
        int res = 0;
        for(int left = 0 ; left < heights.length ; ++left) {
            int minHeight = Integer.MAX_VALUE;
            for(int right = left; right < heights.length ; ++right) {
                minHeight = Math.min(minHeight,heights[right]);
                res = Math.max(res,minHeight * (right - left +1));
            }
        }
        return res;
    }
    // 3. 单调栈
    public int largestRectangleArea(int[] heights) {
        // 利用单调栈确定 left[] right[] 数组
        // left[] : i所在的柱子的左侧小于该柱子高度的柱子下标
        // right[] : i所在的柱子的右侧小于该柱子高度的柱子下标
        int length = heights.length;
        int[] left = new int[length];
        int[] right = new int[length];
        // 单调栈 单调递增 ==> 保证当 curVal > monoStack.peek()时，找到的是第一个小于
        Deque<Integer> monoStack = new LinkedList<>();
        for(int i = 0; i < length; ++i) {
            int curVal = heights[i];
            while(!monoStack.isEmpty() && curVal <= heights[monoStack.peek()]) {
                monoStack.pop();
            }
            left[i] = monoStack.isEmpty()? -1:monoStack.peek();
            monoStack.push(i);
        }
        monoStack.clear();
        // 处理right
        for(int i = length-1;i>=0;i--) {
            int curVal = heights[i];
            while(!monoStack.isEmpty() && curVal <= heights[monoStack.peek()]) {
                monoStack.pop();
            }
            right[i] = monoStack.isEmpty() ? length : monoStack.peek();
            monoStack.push(i);
        }
        // 固定高，计算最大值
        int res = 0 ;
        for(int i = 0; i < length; ++i) {
            // 固定高
            int h = heights[i];
            // 找到该柱子的左侧/右侧最近 小于当前柱子 的柱子
            int leftH = left[i];
            int rightH = right[i];
            res = Math.max(res,h*(rightH-leftH-1));
        }
        return res;
    }

    // 4. 单调栈+常数优化
    public int largestRectangleArea3(int[] heights) {
        int length = heights.length;
        int[] left = new int[length];
        int[] right = new int[length];
        Deque<Integer> monoStack = new LinkedList();
        for(int i =0;i<length; ++i) {
            int curVal = heights[i];
            while(!monoStack.isEmpty() && curVal <= heights[monoStack.peek()]) {
                // h[i] < h[j] ==> i > j ==> h[i]是j右侧最近的小于h[j]的值
                int j = monoStack.pop();
                right[j] = i;
            }
            left[i] = monoStack.isEmpty() ? -1 : monoStack.peek();
            monoStack.push(i);
        }
        // 计算值
        int res = 0 ;
        for(int i = 0; i < length;++i) {
            int h = heights[i];
            int leftH = left[i];
            int rightH = right[i];
            res = Math.max(res,h*(rightH - leftH -1));
        }
        return res;
    }

    /*
    * #problem 239 滑动窗口最大值
    * */
    @Test
    void test(){
        maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3);
    }
    // 1. 单调队列
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> monoQueue = new LinkedList<>();
        int[] res = new int[nums.length - k +1];
        // 初始化滑动数组
        for(int i = 0 ; i<nums.length;i++) {
            if(i<k) {
                addVal(monoQueue,nums[i]);
            } else {
                res[i-k] = monoQueue.getFirst();
                int removeVal = nums[i-k];
                if(removeVal == monoQueue.getFirst()) {
                    monoQueue.removeFirst();
                }
                addVal(monoQueue,nums[i]);
            }
        }
        res[res.length - 1] = monoQueue.getFirst();
        return res;
    }

    private void addVal(Deque<Integer> monoQueue , int val) {
        while(!monoQueue.isEmpty() && val > monoQueue.getLast()) {
            monoQueue.removeLast();
        }
        monoQueue.addLast(val);
    }

    /*
    * #problem 42 接雨水
    * */
    // 1. 遍历高度，当当前柱子的高度小于遍历的高度时，表示可以存水
    // 当当前柱子的高度大于遍历的高度时，需要开始重新计算积水
    public int trap(int[] height) {
        int maxH = 0,length = height.length;
        for(int i =0;i<length;++i) {
            maxH = Math.max(maxH,height[i]);
        }
        int sum = 0;
        for(int curH = 1;curH <= maxH;curH ++) {
            // 找到第一个大于当前高度的柱子，才可以开始存水 （最左边界）
            boolean startCollect = false;
            int tmp = 0;
            for(int i =0;i<length;i++) {
                if(startCollect && height[i] < curH) {
                    tmp++;
                }
                if(height[i] >= curH) {
                    startCollect = true;
                    sum = sum + tmp;
                    tmp = 0;
                }
            }
        }
        return sum;
    }

    @Test
    void test2(){
        trap1(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
    }

    // 2. 固定列，找到该列左边最大高度和右边最大高度
    public int trap1(int[] height) {
        int sum = 0;
        for(int i =0; i<height.length;i++) {
            int h = height[i];
            int left = i-1;
            int leftMaxH = -1;
            // 找的是最高
            while(left >=0) {
                if(height[left] > h) {
                    leftMaxH = Math.max(leftMaxH,height[left]);
                }
                left--;
            }
            if(leftMaxH == -1) {
                continue;
            }
            int right = i+1;
            int rightMaxH = -1;
            while( right < height.length ) {
                if(height[right] > h) {
                    rightMaxH = Math.max(rightMaxH,height[right]);
                }
                right++;
            }
            if(rightMaxH == -1) {
                continue;
            }
            int res = Math.min(leftMaxH,rightMaxH) - h;
            sum += res;
        }
        return sum;

    }

    // 3. 解法2中是要找到 当前索引柱子其左右两端的最高柱子
    // 那我们提前计算出 left[] 和 right[] 就可以了
    // left[i] = Math.max(left[i-1],heights[i-1])
    public int trap2(int[] height) {
        int length = height.length;
        if(length ==0 || length == 1) {
            return 0;
        }
        int[] left = new int[length];
        int[] right = new int[length];
        left[0] = 0;
        right[length-1] = 0;
        for(int i =1;i<length;i++) {
            left[i] = Math.max(left[i-1],height[i-1]);
        }
        for(int i = length-2;i>=0;--i) {
            right[i] = Math.max(right[i+1],height[i+1]);
        }
        int res = 0;
        for(int i =0;i<length;i++) {
            int curH = height[i];
            int temp = Math.min(left[i],right[i]) - curH;
            if(temp > 0) {
                res += temp;
            }
        }
        return res;
    }

    // 4. 单调栈 ==> 找到符合条件的两根柱子
    // height[i] > height[i+1] ~ height[j-1] < height[j]
    // 也就是说，我们按顺序将高度压入栈中，同时保证栈的递减性
    // 当我们发现 h[i] > top , 那么我们可以将h[i]看成右边界，此时如果栈除去栈顶元素还有元素的话，那么栈顶元素之后的那个元素，就是一个左边界
    public int trap3(int[] height) {
        int res = 0;
        Deque<Integer> monoStack = new LinkedList<>();
        for(int i =0;i<height.length;i++) {
            int h = height[i];
            // while循环，一个右边界，可能存在多个左边界可以进行存水操作
            while (!monoStack.isEmpty() && h > height[monoStack.peek()]) {
                int top = monoStack.pop();
                if(monoStack.isEmpty()) {
                    break;
                }
                // top 作为存水的区域，也就是说，计算 top这个位置可以存多高的水
                int left = monoStack.peek();
                int length = i - left -1;
                res += (Math.min(h,height[left]) - height[top])*length;
            }
            monoStack.push(i);
        }
        return res;
    }

    @Test
    void test1(){
        MyCircularDeque1 deque1 = new MyCircularDeque1(77);
        System.out.println(deque1.insertFront(89));;
        System.out.println(deque1.getRear());
        System.out.println(deque1.deleteLast());
        System.out.println(deque1.getRear());
        System.out.println(deque1.insertFront(19));
        System.out.println(deque1.insertFront(23));
        System.out.println(deque1.insertFront(23));
        System.out.println(deque1.insertFront(82));
        System.out.println(deque1.isFull());
        System.out.println(deque1.insertFront(45));
        System.out.println(deque1.isFull());
        System.out.println(deque1.getRear());
        System.out.println(deque1.deleteLast());
        System.out.println(deque1.getFront());
        System.out.println(deque1.getFront());

    }


}
/*
 * #problem 155 最小栈
 * */
// 1. 使用辅助栈
class MinStack{

    private Deque<Integer> data;
    private Deque<Integer> minData;

    public MinStack(){
        data = new LinkedList<>();
        minData = new LinkedList<>();
    }

    public void push(int val){
        data.push(val);
        if(minData.isEmpty() || minData.peek() >= val) {
            minData.push(val);
        }
    }

    public void pop() {
        int val = data.pop();
        if(val == minData.peek()) {
            minData.pop();
        }
    }

    public int top(){
        return data.peek();
    }

    public int getMin(){
        return minData.peek();
    }
}

// 2. 不使用辅助栈 ， 栈中记录 当前val 与 当前栈中的最小值的差值（未压入当前值的栈）
class MinStack1{
    private Deque<Long> data;
    private long min;
    public MinStack1() {
        data = new LinkedList();
    }

    public void push(int val) {
        if(data.isEmpty()) {
            data.push(0L);
            min = val;
        } else {
            data.push((long)val-min);
            min = Math.min(val,min);
        }
    }

    public void pop() {
        long pop = data.pop();
        if(pop < 0) {
            // 当前弹出的元素为栈中最小值，需要更新栈的最小值
            min = min - pop;
        }
    }

    public int top() {
        long pop = data.peek();
        if(pop <= 0 ) return (int)min;
        return (int)(pop + min);
    }

    public int getMin() {
        return (int)min;
    }
}

/*
* #problem 641 设计循环双端队列
* */
class MyCircularDeque {

    /*
    * 观察到这边的函数都是涉及头尾操作的
    * 如果使用数组来作为存储结构的话，可以利用 head 和 tail 用于指向头尾
    * 如果使用链表来作为存储结构的话，就用 head 和 tail指针来维护即可
    * */
    private int capacity;

    private int[] data;

    // 指向头元素
    private int head;
    // 指向末尾元素
    private int tail;

    private int length;


    public MyCircularDeque(int k) {
        this.capacity = k;
        data = new int[k];
        // head 指向当前数组头部的前一位
        head = 0;
        // tail 指向当前数组的尾部
        tail = 0;
        length = 0;
    }

    public boolean insertFront(int value) {
        if(isFull()) {
            return false;
        }
        head = ( head -1 + capacity) % capacity;
        data[head] = value;
        // 因为tail要指向末尾元素，当数组中只有一个元素时，末尾元素与头元素相同
        if(length == 1) tail = head;
        return true;
    }

    public boolean insertLast(int value) {
        if(isFull()) {
            return false;
        }
        tail = ( tail + 1 ) % capacity;
        data[tail] = value;
        length ++;
        if(length == 1) head = tail;
        return true;
    }

    public boolean deleteFront() {
        if(isEmpty()) {
            return false;
        }
        head = (head+1) % capacity;
        length --;
        return true;
    }

    public boolean deleteLast() {
        if(isEmpty()) {
            return false;
        }
        tail = ( tail - 1 + capacity)  % capacity;
        length --;
        return true;
    }

    public int getFront() {
        if(length == 0) {
            return -1;
        }
        return data[head];
    }

    public int getRear() {
        if(length == 0) {
            return -1;
        }
        return data[tail];
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public boolean isFull() {
        return length == capacity;
    }
}


// 链表实现
class MyCircularDeque1 {

    private class DequeNode {
        public int val;
        public DequeNode next,prev;
        public DequeNode(int x ) {
            this.val = x;
        }
        public DequeNode(){}
    }

    private int length;
    private int capacity;
    // 作为哨兵
    private DequeNode head;
    // 指向末尾
    private DequeNode tail;

    public MyCircularDeque1(int k) {
        this.length = 0;
        this.capacity = k;
        head = new DequeNode();
        head.prev = null;
        head.next = head;
        tail = head;
    }

    public boolean insertFront(int value) {
        // 头插法
        if(isFull()) {
            return false;
        }
        DequeNode node = new DequeNode(value);
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
        length ++;
        if(length == 1) tail = node;
        return true;
    }

    public boolean insertLast(int value) {
        if(isFull()) {
            return false;
        }
        DequeNode node = new DequeNode(value);
        node.next = tail.next;
        node.prev = tail;
        tail.next = node;
        tail = node;
        length++;
        return true;
    }

    public boolean deleteFront() {
        if(isEmpty()) {
            return false;
        }
        DequeNode delNode = head.next;
        head.next = delNode.next;
        head.next.prev = head;
        length--;
        if(length == 0) {
            tail = head;
        }
        return true;
    }

    public boolean deleteLast() {
        if(isEmpty()) {
            return false;
        }
        DequeNode delNode = tail;
        tail = tail.prev;
        tail.next = delNode.next;
        delNode.prev = null;
        delNode.next = null;
        length--;
        return true;
    }

    public int getFront() {
        if(isEmpty()) {
            return -1;
        }
        return head.next.val;
    }

    public int getRear() {
        if(isEmpty()) {
            return -1;
        }
        return tail.val;
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public boolean isFull() {
        return length == capacity;
    }
}
